package 排序算法;
/*
* 快排
* */
public class QuickDemo {
    static int[] arr1 = {-9,78,0,23,-567,70};

    public static void main(String[] args) {
        int[] arr2 = new int[8000000];
        for (int i = 0; i < 8000000; i++) {
            arr2[i] = (int)(Math.random()*800000);
        }
        long begin = System.currentTimeMillis();
        QuickSort(arr2,0,arr2.length-1);
        long end = System.currentTimeMillis();
        System.out.println((end-begin));
    }

    public static void QuickSort(int [] arr,int left,int right){
        int l = left;
        int r = right;
        int pivot = arr[(l+r)/2];
        int temp;// 临时变量,用于交换
        while(l<r){
            // 找出左边大于或者等于pivot的值
            while(arr[l] < pivot){
                l+=1;
            }
            // 找出右边小于或者等于pivot的值
            while(arr[r] > pivot){
                r-=1;
            }
            // 相等代表找完了,直接跳出
            if(l == r){
                break;
            }
            // 交换
            temp = arr[l];
            arr[l] = arr[r];
            arr[r] = temp;

            // 如果两边都是pivot相等的值,交换后不变,不加下面两句会死循环
            if(arr[l] == pivot){
                r-=1;
            }

            if(arr[r] == pivot){
                l+=1;
            }
        }

        if(l == r){
            l+=1;
            r-=1;
        }

        if(left < r){
            QuickSort(arr,left,r);
        }

        if(l < right){
            QuickSort(arr,l,right);
        }
    }
    public static void print(int [] arr){
        for (int j : arr) {
            System.out.print(j + " ");
        }
        System.out.println();
    }
}
